package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.TreeNode;
import org.springframework.util.Assert;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName BinaryTreeMaxDepth
 * @Description BinaryTreeMaxDepth
 * @Author wanghaiwei
 * @Date 2022/11/25 16:18
 */
public class BinaryTreeMaxDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    /** 使用广度优先遍历（等同于层次遍历）*/
    public int maxDepthByIterator(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        Queue<TreeNode> nodeDeque = new LinkedList<>();
        nodeDeque.offer(root);
        while(!nodeDeque.isEmpty()) {
            int size = nodeDeque.size();
            while(size > 0) {
                TreeNode curr = nodeDeque.poll();
                if(curr.left != null) {
                    nodeDeque.add(curr.left);
                }
                if (curr.right != null) {
                    nodeDeque.add(curr.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        BinaryTreeMaxDepth solution = new BinaryTreeMaxDepth();
        TreeNode root1 = new TreeNode(3);
        Assert.isTrue(1 == solution.maxDepth(root1), "[3]深度计算错误");

        TreeNode root2 = new TreeNode(3);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(20);
        root2.right.left = new TreeNode(15);
        root2.right.right = new TreeNode(7);
        Assert.isTrue(3 == solution.maxDepth(root2), "[3,9,20,null,null,15,7]深度计算错误");
    }
}
